package org.example.DataStructure.SequenceList;

import java.util.Iterator;

//线性表中顺序表的实现
//使用泛型使得存储多种数据
public class SequenceList<T> implements Iterable<T> {
    //成员变量
    //存储元素的顺序表，数组
    private T[] elements;
    //存储当前顺序表的长度
    private int N;

    //构造方法
    //创建容量为Capacity的顺序表
    public SequenceList(int Capacity) {
        //初始化数组
        this.elements = (T[]) new Object[Capacity];
        //初始化长度
        this.N = 0;

    }

    //空置线性表
    public void clear() {
        //将已有元素置为null方便垃圾回收
        for (int i = 0; i < N; i++) {
            elements[i] = null;
        }
        //将元素数量置为0
        this.N = 0;
    }

    //判断是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //获取线性表中元素的个数
    public int length() {
        return this.N;
    }

    //读取并返回线性表中第i个值
    public T get(int i) {
        //判断i的合法性
        if (i < 0 || i >= this.N) {
            System.err.println("Index out of bounds!");
        }
        return elements[i];
    }

    //在线性表的第i个元素的位置插入一个值为t的数据元素
    public void insert(int i, T t) {
        //先扩容
        upsize();
        //先把i索引以及后面的元素向后移动一位
        for (int j = N; j > i; j--) {
            elements[j] = elements[j - 1];
        }
        //再把元素插入i索引处
        elements[i] = t;
        //更新元素个数
        N++;
    }

    //向线性表中添加一个元素
    public void insert(T t) {
        //扩容后再添加元素
        upsize();
        //添加元素并更新顺序表长度
        elements[N++] = t;
    }

    //删除并返回线性表中的第i个元素
    public T remove(int i) {
        //判断i的合法性
        if (i < 0 || i >= this.N) {
            System.err.println("Index out of bounds!");
        }
        //记录索引i的值
        T current = get(i);
        //将i后面的元素依次向前移动一位
        for (int j = i; j < N - 1; j++) {
            elements[j] = elements[j + 1];
        }
        //元素个数-1
        this.N--;
        //缩容机制
        downsize();
        //返回该元素
        return current;
    }

    //返回线性表中首次出现的指定的数据元素的序号，不存在则返回-1
    public int indexOf(T t) {
        for (int i = 0; i < N; i++) {
            if (elements[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    //重写ToString方法
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < N; i++) {
            sb.append(elements[i]);
            if (i < N - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    //顺序表的遍历
    //先实现Iterable接口，再重写Iterator方法
    @Override
    public Iterator<T> iterator() {
        //利用匿名内部类的方法提供类
        return new Iterator<T>() {
            private int cursor = 0;

            //判断是否有下一个元素
            @Override
            public boolean hasNext() {
                return cursor < N;
            }

            //获取当前容器中的下一个元素
            @Override
            public T next() {
                //获取当前元素并让指针下移
                return elements[cursor++];
            }
        };
    }

    //实现顺序表的容量可变
    //添加元素时候的扩容
    //规则：创建新数组让新数组长度是原数组长度的二倍，再把原数组中的数据添加到新数组中
    //移除元素的缩容，如果发现原数组元素的数量不足数组容量的四分之一则创建一个原数组二分之一容量的新数组储存元素
    //根据参数newsize重置数组的大小的方法
    public void resize(int newsize) {
        //定义一个临时数组指向原数组
        T[] temp = elements;
        //创建一个新数组
        T[] newelements = (T[]) new Object[newsize];
        //将原数组数据拷贝到新数组
        for (int i = 0; i < N; i++) {
            newelements[i] = temp[i];
        }
        elements = newelements;
    }

    //添加元素时的扩容机制的方法
    public void upsize() {
        //如果当前数组满了就扩容
        if (N == elements.length) {
            resize(elements.length * 2);
        }
    }

    //删除元素的缩容机制的方法
    public void downsize() {
        //如果元素数量小于原数组的四分之一就缩容
        if (N < elements.length / 4) {
            resize(elements.length / 2);
        }
    }
}
